package com.yuou.mapper.test;

import java.util.ArrayList;
import java.util.List;

/**
 * 排序工具类
 *
 * @author yuomg
 * @date 2018-10-10
 */
public class SortUtil {
    private static final int BUCKET_NUM = 10;
    
    
    public static void main(String[] args) {
    	List<Integer> arr = new ArrayList<Integer>();
    	arr.add(190);
    	arr.add(991);
    	arr.add(282);
    	arr.add(843);
    	arr.add(339);
    	arr.add(668);
    	arr.add(547);
    	arr.add(798);
    	arr.add(865);
    	arr.add(492);
    	arr.add(584);
    	arr.add(334);
    	arr.add(186);
    	arr.add(128);
    	arr.add(169);
    	arr.add(137);
    	arr.add(295);
    	arr.add(364);
		List<Integer> newArr =radixSort(arr);
		for (int a : newArr) {
			System.out.print(a+",");
		}
	}
    /**
     * 基排序
     * @param arr 待排序数组
     * @return 排好序由小到大的数组
     */
    public static List<Integer> radixSort(List<Integer> arr) {
        // 定义10个桶
        List<List<Integer>> buckets = new ArrayList<>(BUCKET_NUM);
        int radix = 0;

        int maxNumOfRadix;
        while (true) {
            maxNumOfRadix = getPowerNum(radix + 1);
            // 初始化10个数组
            buckets.clear();
            for (int i = 0; i < BUCKET_NUM; i++) {
                //buckets.addAll(new ArrayList<>());
            }

            // 判断当前基是不是最大的
            boolean bucketEnd = true;
            // 第一步，遍历元素，放入对应的桶
            for (Integer item : arr) {
                // 计算元素属于哪个桶
                int radixNum = getRadixNum(item, radix);
                // 放入桶
                buckets.get(radixNum).add(item);

                if (item >= maxNumOfRadix) {
                    bucketEnd = false;
                }
            }

            // 第二步，遍历桶，放回数组，先入桶的先出桶。
            arr.clear();
            for (List<Integer> bucket : buckets) {
                arr.addAll(bucket);
            }

            if (bucketEnd) {
                break;
            } else {
                radix++;
            }
        }

        return arr;
    }

    /**
     * 获取对应基的数字
     * @param num 原始数字
     * @param radix 基：元素的个位、十位、百位，从 0 开始
     * @return 元素对应基的数字，比如 17 的基是 0 的数字是 7
     */
    private static int getRadixNum(int num, int radix) {
        return num / getPowerNum(radix) % 10;
    }

    /**
     * 获取10 的幂
     * @param power 10 的n 次方，从0 开始
     * @return 10 的 power 次方
     */
    private static int getPowerNum(int power) {
        int result = 1;

        for (int i = 1; i <= power; i++) {
            result = result * 10;
        }

        return result;
    }
}
